use std::ptr::{self, null_mut};
use std::sync::atomic::AtomicPtr;
use std::sync::atomic::Ordering::{Relaxed, Release, Acquire};

// 查看 https://stevenbai.top/rust/lock-freedom-without-garbage-collection/

pub struct Stack<T> {
    head: AtomicPtr<Node<T>>
}

impl <T> Stack<T> {

    pub fn new() -> Stack<T> {
        Stack {
            head: AtomicPtr::new(null_mut())
        }
    }

    // 最简单的方法就是从pop开始。 要pop，你只需要循环保存栈顶指针head，然后做一个CAS，用next指针替换当前head
    pub fn pop(&self) -> Option<T> {
        loop {
            // 获取一个快照
            let head = self.head.load(Acquire);
            if head == null_mut() {
                return None;
            } else {
                let next = unsafe {
                    (*head).next
                };
                // 如果快照仍然是好的，从' head '更新到' next '
                match self.head.compare_exchange(head, next, Release, Relaxed) {
                    // ptr::read 函数是 Rust 在没有静态或动态跟踪的情况下提取数据所有权的方法。 在这里，我们使用 compare_exchange 的原子性来保证只有一个线程会调用
                    // ptr::read-正如我们将看到的，这个实现永远不会释放 Nodes，因此数据上的析构函数永远不会被调用。 这两个事实一起使我们使用ptr::read是安全的。
                    Ok(old) => {
                        // 问题是其他线程也可能同时运行 pop。 这些线程可以获得当前head的快照; 
                        // 没有什么可以阻止它们读取(*head).next。 就在我们释放他们指向的节点之后，
                        // 快照上的下一个——一个正在形成的use-after-free bug！
                        break Some(unsafe {ptr::read(&(*old).data)})
                    },
                    Err(_) => continue,
                };
            }
        }
    }

    // push 和pop差不多
    pub fn push(&self, t: T) {
        let new = Box::into_raw(Box::new(Node {
            data: t,
            next: null_mut(),
        }));
        loop {
            // 获取一个快照
            let head = self.head.load(Relaxed);
            // 用快照更新' next '指针
            unsafe {(*new).next = head;}
            match self.head.compare_exchange(head, new, Release, Release) {
                Ok(_) => break (),
                Err(_) => continue,
            }
        }
    }
}

struct Node<T> {
    data: T,
    next: *mut Node<T>,
}

// 如果是支持GC的语言编写了上面的代码,那么我们已经实现了一个lock-free stack,但是在rust中不行,因为它发生了内存泄漏
// 特别是，当Node指针从堆栈中移除后，pop实现不会尝试释放它。

// 问题是其他线程也可能同时运行 pop。 这些线程可以获得当前head的快照; 
// 没有什么可以阻止它们读取(*head).next。 就在我们释放他们指向的节点之后，
// 快照上的下一个——一个正在形成的use-after-free bug！

// 对于无锁代码，有几种不是基于 gc 的内存管理方法，但它们都归结为相同的核心特点:
// 可达性有两个来源——数据结构和访问它的线程中的快照(引用)。 在删除一个节点之前，我们需要知道它不能以这两种方式中的任何一种方式到达。
// 一旦一个节点从数据结构中解除链接，就不会创建到达该节点的新快照(引用)。

// 其中一个最优雅和有希望的回收方案是Keir Fraser’s epoch-based reclamation，这来自于他的博士论文。
// https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.pdf
// 其基本思想是将未与数据结构链接的节点(可达性的第一个来源)隐藏起来，直到可以安全地删除它们。
// 在删除隐藏的节点之前，我们需要知道当时访问数据结构的所有线程都已经完成了它们正在执行的操作。
// 通过上面的特点2，这将意味着不再有任何引用留下(因为在此期间不可能创建新的引用)。
// 最困难的部分是在不同步的情况下完成所有这些工作。 否则，我们就失去了lock-free应该带来的好处！

// epoch的工作原理是:
// A 全局epoch计数器(取值0、1和2) ;
// A global list of garbage for each epoch;每个opoch都有一个全局垃圾列表;
// 每个线程的“活动”标志;
// 每个线程的epoch计数器